package trees;

public class MakeRoot {

	static class Node {

		public Node(int p) {
			this.val = p;
		}

		int val;
		Node parent, left, right;
	}

	/**
	 * Given a binary Search tree and a Node, How would you transform the tree
	 * to make that Node as root.The resulting tree should be a BST. 14
	 */
	public static void main(String[] args) {

		Node n1 = new Node(1);
		Node n2 = new Node(5);
		Node n3 = new Node(7);
		Node n4 = new Node(6);
		Node n5 = new Node(9);
		Node n6 = new Node(14);
		Node n7 = new Node(11);
		Node n8 = new Node(20);

		n5.left = n2;
		n5.right = n6;
		n6.parent = n5;
		n2.parent = n5;

		n2.left = n1;
		n1.parent = n2;
		n2.right = n3;
		n3.parent = n2;
		n3.left = n4;
		n4.parent = n3;
		n6.right = n8;
		n8.parent = n6;
		n6.left = n7;
		n7.parent = n6;

		// preOrderTraversal(n5);

		makeRoot(n3);

		//leftRotation(n3);

		preOrderTraversal(n3);

	}

	private static void preOrderTraversal(Node n) {
		if (n != null) {
			System.out.println(n.val);
			preOrderTraversal(n.left);
			preOrderTraversal(n.right);
		}
	}

	public static void makeRoot(Node n) {

		if (n == null) {
			return;
		}

		while (n.parent != null) {

			if (n.parent.left != null && n.parent.left == n) {
				rightRotation(n);
			} else {
				leftRotation(n);
			}
		}
	}

	public static void rightRotation(Node node) {

		Node parent = node.parent;

		node.parent = parent.parent;
		parent.parent = node;
		parent.left = node.right;
		node.right = parent;

		changeParentLink(node, parent);

	}

	private static void changeParentLink(Node node, Node parent) {

		if (node.parent != null) {
			if (node.parent.left == parent) {
				node.parent.left = node;
			} else {
				node.parent.right = node;
			}
		}
	}

	public static void leftRotation(Node node) {
		Node parent = node.parent;

		node.parent = parent.parent;
		parent.parent = node;
		parent.right = node.left;
		node.left = parent;

		changeParentLink(node, parent);

	}

}
